package solution._0330._0337;

import common.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created by chen_snow
 * Date: 2021/7/7 23:50
 * Description: 打家劫舍 III
 */
public class Solution {
    public int rob(TreeNode root) {
        int[] result = robSub(root);
        return Arrays.stream(result).max().getAsInt();
    }

    public int[] robSub(TreeNode root) {
        if (root == null) {
            return new int[]{0, 0};
        }

        if (root.left == null && root.right == null) {
            return new int[]{root.val, 0};
        }

        int[] left = robSub(root.left);
        int[] right = robSub(root.right);


        return new int[]{left[1] + right[1] + root.val, Math.max(left[0], left[1]) + Math.max(right[0], right[1])};
    }
}
